home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1996 June / EnigmA AMIGA RUN 08 (1996)(G.R. Edizioni)(IT)[!][issue 1996-06][EARSAN CD VII].iso / earcd / gcc / ixemlsrc.lha / ixemul / ixnet / lrucache.c < prev    next >
C/C++ Source or Header  |  1996-03-13  |  10KB  |  380 lines
  1. /*-
  2.  * Copyright (c) 1990 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Mike Olson.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. char sccsid[] = "@(#)lrucache.c    5.3 (Berkeley) 2/22/91";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. /*
  42.  *  lrucache.c -- LRU cache for disk-based btree pages.
  43.  *
  44.  *    This file implements an LRU cache in user space for disk-based
  45.  *    btrees.
  46.  */
  47. #define KERNEL
  48. #include "ixnet.h"
  49. #include <sys/param.h>
  50. #include <stdlib.h>
  51. #include <string.h>
  52. #include <unistd.h>
  53. #include "lrucache.h"
  54.  
  55. /*
  56.  *  LRUINIT -- Initialize a new LRU cache.
  57.  *
  58.  *    There's a separate LRU cache for every open file descriptor on which
  59.  *    the user wants caching.  The desired cache size and logical page
  60.  *    size are passed in.  We try to avoid growing the cache beyond the
  61.  *    limit specified by the user, but if we cannot satisfy a block request
  62.  *    without growing the cache, we do so.
  63.  *
  64.  *    Note that the page size passed in is the logical page size for
  65.  *    use with this file descriptor, and doesn't necessarily have anything
  66.  *    to do with the underlying hardware page size.
  67.  *
  68.  *    Parameters:
  69.  *        fd -- file descriptor for this cache
  70.  *        cachesz -- number of buffers in cache (suggested)
  71.  *        pagesz -- logical page size inside this file
  72.  *        inproc -- routine to call when a buffer is read
  73.  *        outproc -- routine to call when a buffer is written
  74.  *
  75.  *    Returns:
  76.  *        Opaque pointer to the LRU cache on success, NULL on failure.
  77.  *
  78.  *    Side Effects:
  79.  *        Allocates memory for the hash table and LRU cache.  Buffers
  80.  *        are allocated on demand, later.
  81.  */
  82. LRU
  83. lruinit(fd, cachesz, pagesz, opaque, inproc, outproc)
  84.     int fd;
  85.     int cachesz;
  86.     int pagesz;
  87.     char *opaque;
  88.     int (*inproc)();
  89.     int (*outproc)();
  90. {
  91.     register LRUCACHE *l;
  92.     int nbytes;
  93.  
  94.     /* allocate the LRU cache struct */
  95.     if ((l = (LRUCACHE *) malloc((unsigned) sizeof(LRUCACHE)))
  96.         == (LRUCACHE *) NULL)
  97.         return ((LRU) NULL);
  98.  
  99.     /* allocate the hash table */
  100.     nbytes = cachesz * sizeof(CACHE_ENT *);
  101.     if ((l->lru_cache = (CACHE_ENT **) malloc((unsigned) nbytes))
  102.         == (CACHE_ENT **) NULL) {
  103.         (void) free((char *) l);
  104.         return ((LRU) NULL);
  105.     }
  106.  
  107.     /* init memory */
  108.     bzero((char *) (l->lru_cache), (size_t) nbytes);
  109.     l->lru_fd = fd;
  110.     l->lru_psize = pagesz;
  111.     l->lru_csize = cachesz;
  112.     l->lru_cursz = 0;
  113.     l->lru_opaque = opaque;
  114.     l->lru_head = l->lru_tail = (LRU_ENT *) NULL;
  115.     l->lru_inproc = inproc;
  116.     l->lru_outproc = outproc;
  117.  
  118.     return ((LRU) l);
  119. }
  120.  
  121. /*
  122.  *  LRUGET -- Get a buffer from an LRU cache.
  123.  *
  124.  *    If the buffer is not in the cache at present, this routine will
  125.  *    instantiate it from the file.  This REQUIRES that the desired
  126.  *    block actually be on disk; we don't do non-blocking reads, so
  127.  *    if it's not actually out there, this routine won't return for
  128.  *    a very long time.  In order to instantiate a new buffer, use
  129.  *    lrugetnew().
  130.  *
  131.  *    Parameters:
  132.  *        lru -- the LRU cache to use.
  133.  *        pgno -- the logical block number to get.
  134.  *        nread -- pointer to an int, in which the number of bytes
  135.  *             read is returned.
  136.  *
  137.  *    Returns:
  138.  *        (char *) pointer to the buffer for the desired block.  The
  139.  *        number of bytes actually read is returned in *nread.
  140.  *
  141.  *    Warnings:
  142.  *        The requested buffer is locked down until the user does
  143.  *        an explicit lrurelease() on it.
  144.  */
  145.  
  146. char *
  147. lruget(lru, pgno, nread)
  148.     LRU lru;
  149.     int pgno;
  150.     int *nread;
  151. {
  152.     LRUCACHE *l = (LRUCACHE *) lru;
  153.     CACHE_ENT *ce;
  154.     LRU_ENT *lruent;
  155.     char *buffer;
  156.     long pos;
  157.  
  158.     /* is it already in the cache? */
  159.     if ((ce = lruhashget(l, pgno)) != (CACHE_ENT *) NULL) {
  160.  
  161.         /* yes, move it to the head and return it */
  162.         lruent = ce->c_lruent;
  163.         lruent->l_flags &= ~LRU_FREE;
  164.         lruhead(l, ce->c_lruent);
  165.         *nread = l->lru_psize;
  166.         return (ce->c_lruent->l_buffer);
  167.     }
  168.  
  169.     /* not there, get a free page */
  170.     if ((buffer = lrugetpg(l, pgno, nread, lruget)) == (char *) NULL)
  171.         return ((char *) NULL);
  172.  
  173.     /* okay, got a buffer -- fill it */
  174.     pos = (long) (l->lru_psize * pgno);
  175.     if (lseek(l->lru_fd, pos, L_SET) != pos)
  176.         return ((char *) NULL);
  177.  
  178.     *nread = read(l->lru_fd, buffer, l->lru_psize);
  179.  
  180.     if (l->lru_inproc)
  181.         (*(l->lru_inproc))(buffer, l->lru_opaque);
  182.  
  183.     return (buffer);
  184. }
  185.  
  186. /*
  187.  *  LRUGETNEW -- Get a page for a new block in an LRU cache.
  188.  *
  189.  *    This routine allows users to instantiate pages for a file if they
  190.  *    don't exist on disk yet.  It's used to make a file bigger.
  191.  *
  192.  *    Parameters:
  193.  *        lru -- the LRU cache to use
  194.  *        pgno -- the (new) logical page number to instantiate
  195.  *        nread -- ptr to int to get number of bytes read (this is
  196.  *             guaranteed to be zero, since the page isn't on disk)
  197.  *
  198.  *    Returns:
  199.  *        Pointer to a buffer for the associated page, or NULL on
  200.  *        failure.
  201.  *
  202.  *    Warnings:
  203.  *        The associated buffer is locked down until the user
  204.  *        explicitly does an lrurelease() on it.
  205.  */
  206.  
  207. char *
  208. lrugetnew(lru, pgno, nread)
  209.     LRU lru;
  210.     int pgno;
  211.     int *nread;
  212. {
  213.     LRUCACHE *l = (LRUCACHE *) lru;
  214.  
  215.     *nread = 0;
  216.     return (lrugetpg(l, pgno, nread, lrugetnew));
  217. }
  218.  
  219. /*
  220.  *  LRUFLUSH -- flush an LRU page to disk.
  221.  *
  222.  *    This routine forces a page to disk.  Users should use lruwrite(),
  223.  *    which simply marks a page dirty and does late writing.
  224.  *
  225.  *    Parameters:
  226.  *        l -- LRU cache
  227.  *        lruent -- the LRU cache entry whose page we should flush
  228.  *
  229.  *    Returns:
  230.  *        Zero on success, -1 on failure.
  231.  */
  232. int
  233. lruflush(l, lruent)
  234.     LRUCACHE *l;
  235.     LRU_ENT *lruent;
  236. {
  237.     long pos;
  238.  
  239.     if (l->lru_outproc)
  240.         (*(l->lru_outproc))(lruent->l_buffer, l->lru_opaque);
  241.  
  242.     pos = (long) (l->lru_psize * lruent->l_pgno);
  243.     if (lseek(l->lru_fd, pos, L_SET) != pos)
  244.         return (-1);
  245.     if (write(l->lru_fd, lruent->l_buffer, l->lru_psize) != l->lru_psize)
  246.         return (-1);
  247.  
  248.     if (l->lru_inproc)
  249.         (*(l->lru_inproc))(lruent->l_buffer, l->lru_opaque);
  250.  
  251.     lruent->l_flags &= ~LRU_DIRTY;
  252.     return (0);
  253. }
  254.  
  255. /*
  256.  *  LRUWRITE -- Mark an LRU cache buffer dirty
  257.  *
  258.  *    This routine is how users should move their changes to disk.  The
  259.  *    cache code marks the associated buffer dirty, and flushes it to
  260.  *    disk if we need to reuse the buffer for some other page.
  261.  *
  262.  *    Parameters:
  263.  *        lru -- LRU cache
  264.  *        pgno -- page number to flush
  265.  *
  266.  *    Returns:
  267.  *        Zero on success, -1 on failure.
  268.  */
  269.  
  270. int
  271. lruwrite(lru, pgno)
  272.     LRU lru;
  273.     int pgno;
  274. {
  275.     LRUCACHE *l = (LRUCACHE *) lru;
  276.     CACHE_ENT *ce;
  277.  
  278.     if ((ce = lruhashget(l, pgno)) == (CACHE_ENT *) NULL)
  279.         return (-1);
  280.  
  281.     /* mark the entry dirty */
  282.     ce->c_lruent->l_flags |= LRU_DIRTY;
  283.  
  284.     return (0);
  285. }
  286.  
  287. /*
  288.  *  LRUSYNC -- Flush all changes to disk
  289.  *
  290.  *    This routine allows users to force all changes to buffers currently
  291.  *    in memory to disk.  This is expensive.
  292.  *
  293.  *    Parameters:
  294.  *        lru -- LRU cache to flush
  295.  *
  296.  *    Returns:
  297.  *        Zero on success, -1 on failure
  298.  *
  299.  *    Side Effects:
  300.  *        After this call, all buffers are clean.
  301.  */
  302.  
  303. int
  304. lrusync(lru)
  305.     LRU lru;
  306. {
  307.     LRUCACHE *l = (LRUCACHE *) lru;
  308.     LRU_ENT *le;
  309.  
  310.     for (le = l->lru_head; le != (LRU_ENT *) NULL; le = le->l_next)
  311.         if (le->l_flags & LRU_DIRTY)
  312.             if (lruflush(l, le) < 0)
  313.                 return (-1);
  314.     return (0);
  315. }
  316.  
  317. /*
  318.  *  LRURELEASE -- Release a buffer in the LRU cache for reuse
  319.  *
  320.  *    When the user does an lruget() or lrugetnew(), the buffer we return
  321.  *    is locked down, to guarantee that it's not reused while the user
  322.  *    still needs it.  Once a buffer is no longer needed, it should be
  323.  *    released (via this routine) so that we can use it for other pages
  324.  *    if necessary.
  325.  *
  326.  *    Parameters:
  327.  *        lru -- LRU cache
  328.  *        pgno -- page number of buffer to release
  329.  *
  330.  *    Returns:
  331.  *        Zero on success, -1 on failure
  332.  */
  333.  
  334. int
  335. lrurelease(lru, pgno)
  336.     LRU lru;
  337.     int pgno;
  338. {
  339.     LRUCACHE *l = (LRUCACHE *) lru;
  340.     CACHE_ENT *ce;
  341.  
  342.     if ((ce = lruhashget(l, pgno)) == (CACHE_ENT *) NULL)
  343.         return (-1);
  344.     ce->c_lruent->l_flags |= LRU_FREE;
  345.     return (0);
  346. }
  347.  
  348. /*
  349.  *  LRUFREE -- Free an entire LRU cache
  350.  *
  351.  *    This routine releases an LRU cache.  The cache should not be
  352.  *    used again.
  353.  *
  354.  *    Parameters:
  355.  *        lru -- LRU cache to free
  356.  *
  357.  *    Returns:
  358.  *        None.
  359.  *
  360.  *    Side Effects:
  361.  *        Frees a lot of memory.
  362.  */
  363.  
  364. void
  365. lrufree(lru)
  366.     LRU lru;
  367. {
  368.     LRUCACHE *l = (LRUCACHE *) lru;
  369.     LRU_ENT *le;
  370.     LRU_ENT *sle;
  371.  
  372.     for (le = l->lru_head; le != (LRU_ENT *) NULL; ) {
  373.         free((char *) (le->l_buffer));
  374.         sle = le;
  375.         le = le->l_next;
  376.         free((char *) sle);
  377.     }
  378.     free ((char *) l);
  379. }
  380.